package com.leetcode.algorithm.y22.m06;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
 * 
 * @author jie.deng
 *
 */
class Question0034Solution01 {

	public int[] searchRange(int[] nums, int target) {
		if (nums.length == 0) {
			return new int[] { -1, -1 };
		}
		// 找等于target的值的索引
		int left = 0;
		int right = nums.length - 1;
		int mid = 0;
		while (left <= right) {
			mid = left + ((right - left) >> 1);
			if (nums[mid] == target) {
				break;
			} else if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		if (nums[mid] != target) {
			return new int[] { -1, -1 };
		}

		// 备份
		int r = right;
		int m = mid;

		// 找第一个等于target的值的索引
		right = mid;
		while (left < right) {
			mid = left + ((right - left) >> 1);
			if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		int l = left;

		// 找最后一个等于target的值的索引
		right = r;
		left = m;
		while (left < right) {
			mid = left + ((right - left) >> 1);
			if (nums[mid] > target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		r = nums[right] == target ? right : right - 1;

		return new int[] { l, r };
	}

}